/*
https://leetcode-cn.com/problems/rotate-list/
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 (即将最后一个节点移动到头结点, 重复k次)

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

输入：head = [0,1,2], k = 4
输出：[2,0,1]
* */

//时间复杂度：O(n)O(n)，最坏情况下，我们需要遍历该链表两次。
//空间复杂度：O(1)O(1)，我们只需要常数的空间存储若干变量。

//1. 将链表尾节点 连接到 头节点, 组成一个环
//2. 找到旋转后的链表头节点的前一个节点
//3. 拆环, 返回头结点
//详见 README.md

const rotateRight = function (head, k) {
  if (k === 0 || !head || !head.next) {
    return head;
  }
  //1. 将链表尾节点 连接到 头节点, 组成一个环
  let tail = head;
  let len = 1;
  while (tail.next){
    tail = tail.next;
    len++;
  }
  if(k === len){ //旋转len次 和 不旋转 是一个结果, 比如 1 2 3, 转3次, 还是 1 2 3
    return head;
  }
  tail.next = head;
  //--- --- ---/


  //2. 找到旋转后的链表头节点的前一个节点
  let n = len - (k % len); //我们不需要重复转圈, 只需要落到最终的结果即可, 故用%
  let pre = head, ret;

  while (--n > 0) { //用--n 这样能少一次 就刚好落在新的头结点的前一个
    pre = pre.next;
  }
  // ret指向新的头节点
  ret = pre.next
  //--- --- ---/


  //3. 拆环, 返回头结点
  // 将环拆开
  pre.next = null;
  return ret;
};
